1. Field of the Invention
The present invention relates to an error detection technique, particularly to a CRC (Cyclic Redundancy Checking) value calculator that uses cyclic codes for detecting and correcting errors in network related fields, particularly in data communications.
2. Description of the Prior Art
Cyclic code systems are well-known. How they work is that a code polynomial in which the bits of each codeword are the coefficients is divided by a generator polynomial to obtain remainder coefficients that form check bits. Then, when the codewords and the check bits are transmitted along a transmission channel in which communication errors may occur, at the receiving side, errors in transmission can be detected from the remainder obtained when the polynomial corresponding to the received information is divided by the same generator polynomial, enabling the received data to be corrected. Such cyclic code systems are used in magnetic storage devices and commercial data network devices.
CRC (Cyclic Redundancy Checking) is one error checking system. It is noted for its use of compacted cyclic codes. It is extensively employed for error checking in serial transmission channels, because it facilitates burst error detection and can be readily implemented in hardware. It is used for checking frame data in Ethernet (TM) systems. An example is 32-bit-long CRC-32 used for the FCS (Frame Check Sequence) of network frames.
FIG. 9 shows a LFSR (Linear Feedback Shift Register) which is a simple CRC circuit. This is a well-known circuit that performs CRC calculations during each clock cycle, one bit at a time.
Research continues to be carried out aimed at improving the processing performance of CRC circuitry. For example, since the unit of network frame data is the byte, research is being carried out into CRC-32 circuits that calculate the CRC value per byte. FIG. 10 shows an example of a CRC-32 circuit. The circuit shown uses exclusive OR to calculate CRC values from 8-bit data inputs. The length of the data that is processed per cycle is fixed; this 8-bit processing CRC circuit cannot calculate a CRC value from 5-bit data, for example.
Network speeds continue to improve, as shown by the recent appearance of 10-gigabit Ethernet (registered trademark), and is driving a need to similarly improve the throughput of CRC calculation processing. As a result, CRC calculators have been developed with improved throughputs that are able to process multiple bytes of data per cycle. The lengths of the data that can be processed by these calculators per cycle is fixed, and the calculators are comprised of these basic CRC circuits.
FIG. 1 shows an example of the configuration of a conventional CRC-32 calculator, in this case one in which the process data width is eight bytes per cycle. The calculator is comprised of eight CRC circuits. Including CRC circuits for processing data having widths of from one to eight bytes makes it possible to calculate the correct CRC value by selecting the CRC value result corresponding to the byte length of the remainder, even when input network data frames have remainders that are not 8-byte multiples.
FIG. 11 is a block diagram showing the configuration of a CRC-32 value calculator that is a generalized implementation of the configuration of FIG. 1, shown during the calculation of m2n bits. By including CRC circuits for data widths m, 2m, . . . , m2n, it is possible to calculate the correct CRC value by selecting the CRC value result corresponding to the remainder byte length.
However, in the case of these circuit configurations, increased data widths are handled by scaling up the circuitry by increasing the number of CRC circuits. This increase is accompanied by an increase in the number of CRC value selector inputs, increasing the circuit delay. When the data width is increased in the case of the conventional technology, a CRC calculator that processes m2n bits of data per cycle is configured using m2n basic CRC circuits. For example, a CRC calculator that processes a data width of 2n bytes per cycle is comprised of 2n basic CRC circuits consisting of
a CRC circuit that processes every 2n bytes,
a CRC circuit that processes every 2n−1 bytes, . . . ,
a CRC circuit that processes every one byte.
Therefore, if, for example, the width of the data processed by the CRC calculator is doubled, the number of basic CRC circuits constituting the calculator is also doubled, increasing the relative scale of the circuitry.
With respect to differences between the prior art and the present invention arising from differences in the scale of the circuitry, while with a conventional configuration the size of a CRC circuit is 2n, the size of a circuit is (n+1) in the case of the configuration of the present invention. The number of CRC circuits is a logarithmic scale, and the latency only increases by the amount of the logarithmic scale.
JP-A 2002-359561 discloses a CRC calculator that can receive variable-length data for processing. However, the CRC calculator comprises an input data shift circuit, a masking circuit and a CRC arithmetic unit.
The CRC calculator of the present invention comprises a number of CRC circuits that is a logarithmic order of the input data width, and selectors possessing registers, connected in series, and as such has a configuration that is different from that of JP-A 2002-359561.